﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace MPlusTree
{
    public class MPTree<Key>
        where Key:MPKey, new()
    {
        #region Member variables
        private static int MAX_NUM_ENTRIES = 30;
        private int CURRENT_LEVEL = 0;

        private bool isOpen;
        private MPStore store;
        private int pageSize = 4096;

        #endregion

        #region Create, Open, Close M+ tree
        public MPTree(int pageSize)
        {
            isOpen = false;
            store = null;
            this.pageSize = pageSize;
        }

        public MPTree()
        {
            isOpen = false;
            store = null;
        }

        public void CreateTree(string name, int maxEntries)
        {
            if (IsOpen()) return;
            MAX_NUM_ENTRIES = maxEntries;
            store = CreateStore();
            store.Create(name);

            if (!store.IsOpen()) return;

            //Add parent of root node
            ulong page = store.Allocate();
            MPNode<Key> node1 = NewNode(this);
            node1.SetPage(page);
            node1.SetLevel(CURRENT_LEVEL + 1);

            /*
            MPEntry rootEntry = new MPEntry();
            rootEntry.SetLeftPage(store.Allocate());
            node.AddEntry(rootEntry);
            */
            WriteNode(node1);

            //Add root node
            page = store.Allocate();
            MPNode<Key> node2 = NewNode(this);
            node2.SetPage(page);
            node2.SetLevel(CURRENT_LEVEL);
            node2.SetParentPage(node1.GetPage());
            WriteNode(node2);

            ++CURRENT_LEVEL;
            isOpen = true;
        }

        public void OpenTree(string name)
        {
            if (IsOpen()) return;
            store = CreateStore();
            store.Open(name);
            
            if (!store.IsOpen()) return;
            isOpen = true;
            
        }

        private MPNode<Key> NewNode(MPTree<Key> tree)
        {
            MPNode<Key> node = CreateNode();
            node.SetTree(tree);
            return node;
        }

        private MPNode<Key> CreateNode()
        {
            MPNode<Key> node = new MPNode<Key>(MPTree<Key>.MAX_NUM_ENTRIES);
            return node;
        }

        private MPStore CreateStore()
        {
            return new MPStore(pageSize);
        }

        private bool IsRoot(MPNode<Key> node)
        {
            return CURRENT_LEVEL == node.GetLevel();
        }

        private ulong GetRootPage()
        {
            return 2;
        }

        private bool IsOpen()
        {
            return isOpen;
        }

        public void Close()
        {
            store.Close();
        }

        #endregion

        #region Disk access
        public MPNode<Key> ReadNode(ulong page)
        {
            byte[] buff = new byte[store.PageSize()];
            store.Read(page, buff);
            MPNode<Key> node = new MPNode<Key>();
            node.UnPack(buff);
            node.SetTree(this);

            return node;
        }

        public void WriteNode(MPNode<Key> node)
        {
            byte[] buff = new byte[store.PageSize()];
            node.Pack(buff);
            store.Write(node.GetPage(), buff);
        }

        public void DeleteNode(MPNode<Key> node)
        {
            store.Deallocate(node.GetPage());
        }

        #endregion

        #region Update key dimension & radius
        private bool UpdateKeyDim(MPEntry<Key> parent, MPEntry<Key> child)
        {
            if (parent.GetRightPage() != 0)
            {
                ulong childPage = child.GetNode().GetPage();

                if (parent.GetLeftPage() == childPage)
                {
                    float lMax = float.MinValue;
                    float lMin = float.MaxValue;
                    FindMaxMinDimVal(child.GetNode(), parent.GetKey().GetDNO(), ref lMax, ref lMin);

                    if (parent.GetLeftMax() < lMax)
                    {
                        parent.SetLeftMax(lMax);
                        return true;
                    }
                }
                else if (parent.GetRightPage() == childPage)
                {
                    float rMax = float.MinValue;
                    float rMin = float.MaxValue;
                    FindMaxMinDimVal(child.GetNode(), parent.GetKey().GetDNO(), ref rMax, ref rMin);
                    if (parent.GetRightMin() > rMin)
                    {
                        parent.SetRightMin(rMin);
                        return true;
                    }
                }
            }

            return false;
        }

        void UpdateRadiusAndKeyDim(ulong page, int pos)
        {
            MPNode<Key> node = ReadNode(page);

            MPEntry<Key> parent = node.GetEntries()[pos];
            MPEntry<Key> child;

            float tmp;
            bool loop = true;
            while (!IsRoot(parent.GetNode()))
            {
                child = parent;
                node = ReadNode(child.GetNode().GetParentPage());
                parent = node.GetEntries()[child.GetNode().GetParentPos()];

                if (loop)
                {
                    tmp = child.GetDisToParent() + child.GetRadius();
                    if (parent.GetRadius() < tmp)
                    {
                        parent.SetRadius(tmp);
                    }
                    else
                    {
                        loop = false;
                    }
                }

                if (UpdateKeyDim(parent, child) || loop == true)
                    WriteNode(parent.GetNode());
            }
        }

        #endregion

        #region Store entry
        public void StoreEntry(MPNode<Key> node, MPEntry<Key> entry)
        {
            MPNode<Key> parentNode = ReadNode(node.GetParentPage());
            
            if (IsRoot(parentNode) && node.GetNumEntries() == 0)//store to empty tree
            {
                MPEntry<Key> cloneEntry = entry.Clone();
                cloneEntry.SetLeftPage(node.GetPage());
                cloneEntry.SetRightPage(0);
                cloneEntry.SetRadius(0);
                cloneEntry.SetDisToParent(0);
                cloneEntry.SetLeftMax(float.MinValue);
                cloneEntry.SetRightMin(float.MaxValue);
                parentNode.AddEntry(cloneEntry);
                
                node.SetParentPos(cloneEntry.GetPos());
                WriteNode(parentNode);
            }

            MPEntry<Key> parentEntry = parentNode.GetEntries()[node.GetParentPos()];
            entry.SetDisToParent(entry.GetKey().Distance(parentEntry.GetKey()));

            node.AddEntry(entry);
            WriteNode(node);
            UpdateRadiusAndKeyDim(node.GetPage(), entry.GetPos());
        }

        #endregion

        #region Reallocate
        //void Reallocate(MPEntry<Key> rootEntry, MPEntry<Key> newEntry)
        //{
        //    MPNode<Key> nodeLeft = ReadNode(rootEntry.GetLeftPage());
        //    ulong twinAddr = nodeLeft.IsFull() ? rootEntry.GetRightPage() : rootEntry.GetLeftPage();

        //    MPNode<Key> node;
        //    if (twinAddr != nodeLeft.GetPage())
        //        node = ReadNode(twinAddr);
        //    else node = nodeLeft;
            
        //    node.AddEntry(newEntry, true);
        //    WriteNode(node);
 
        //    UpdateRadiusAndKeyDim(node.GetPage(), newEntry.GetPos());
        //}

        //void Reallocate(MPEntry<Key> rootEntry, MPEntry<Key> newEntry)
        //{
        //    MPNode<Key> nodeLeft = ReadNode(rootEntry.GetLeftPage());
        //    MPNode<Key> nodeRight = ReadNode(rootEntry.GetRightPage());

        //    int n = 0;
        //    int max;
        //    MPEntry<Key>[] arrEntries = new MPEntry<Key>[MAX_NUM_ENTRIES << 1];
        //    MPEntry<Key>[] entries = nodeLeft.GetEntries();
        //    max = nodeLeft.GetNumEntries();
        //    int i;
        //    for (i = 0; i < max; ++i)
        //    {
        //        arrEntries[n] = entries[i];
        //        ++n;
        //    }

        //    max = nodeRight.GetNumEntries();
        //    entries = nodeRight.GetEntries();
        //    for (i = 0; i < nodeRight.GetNumEntries(); ++i)
        //    {
        //        arrEntries[n] = entries[i];
        //        ++n;
        //    }
        //    arrEntries[n] = newEntry;
        //    ++n;

        //    //Clear nodeLeft and nodeRight
        //    nodeLeft.SetNumEntries(0);
        //    nodeRight.SetNumEntries(0);

        //    //Redistribute(like SplitKeyDim)
        //    SortKeyDim(arrEntries, n, rootEntry.GetKey().GetDNO());

        //    max = (n >> 1);
        //    float lMax = float.MinValue;
        //    float rMin = float.MaxValue;
        //    for (i = 0; i < max; ++i)
        //    {
        //        if (newEntry == arrEntries[i])
        //            nodeLeft.AddEntry(arrEntries[i], true);//Add and update radius of arrNodes[i]
        //        else
        //            nodeLeft.AddEntry(arrEntries[i]);

        //        //calc lMax
        //        if (lMax < arrEntries[i].GetKey().GetDimensionValue(rootEntry.GetKey().GetDNO()) + arrEntries[i].GetRadius())
        //            lMax = arrEntries[i].GetKey().GetDimensionValue(rootEntry.GetKey().GetDNO()) + arrEntries[i].GetRadius();
        //    }


        //    for (i = max; i < n; ++i)
        //    {
        //        if (newEntry == arrEntries[i])
        //            nodeRight.AddEntry(arrEntries[i], true);//Add and update radius of arrNodes[i]
        //        else
        //            nodeRight.AddEntry(arrEntries[i]);

        //        //calc rMin
        //        if (rMin > arrEntries[i].GetKey().GetDimensionValue(rootEntry.GetKey().GetDNO()) - arrEntries[i].GetRadius())
        //            rMin = arrEntries[i].GetKey().GetDimensionValue(rootEntry.GetKey().GetDNO()) - arrEntries[i].GetRadius();
        //    }

        //    //Update key dimension lMax, rMin
        //    MPEntry<Key> entry1 = null;
        //    if (nodeLeft.GetNumEntries() > 0)
        //    {
        //        rootEntry.SetLeftMax(lMax);
        //    }

        //    MPEntry<Key> entry2 = null;
        //    if (nodeRight.GetNumEntries() > 0)
        //    {
        //        rootEntry.SetRightMin(rMin);
        //    }

        //    // Determine if the left and right subtwin of a node are leaves or not
        //    if (entry1 != null && (entry1.GetLeftPage() == 0 &&
        //        entry1.GetRightPage() == 0))
        //    {
        //        nodeLeft.SetLevel(0);
        //        nodeRight.SetLevel(0);
        //    }
        //    else if (entry2 != null && (entry2.GetLeftPage() == 0 &&
        //        entry2.GetRightPage() == 0))
        //    {
        //        nodeLeft.SetLevel(0);
        //        nodeRight.SetLevel(0);
        //    }

        //    WriteNode(rootEntry.GetNode());
        //    WriteNode(nodeLeft);
        //    WriteNode(nodeRight);

        //    UpdateRadiusAndKeyDim(newEntry.GetNode().GetPage(), newEntry.GetPos());
        //}
        

        //New

        void Reallocate(MPEntry<Key> rootEntry, MPEntry<Key> newEntry)
        {
            MPNode<Key> nodeLeft = ReadNode(rootEntry.GetLeftPage());
            MPNode<Key> nodeRight = ReadNode(rootEntry.GetRightPage());

            int n = 0;
            int max;
            MPEntry<Key>[] arrEntries = new MPEntry<Key>[MAX_NUM_ENTRIES << 1];
            MPEntry<Key>[] entries = nodeLeft.GetEntries();
            max = nodeLeft.GetNumEntries();
            int i;
            for (i = 0; i < max; ++i)
            {
                arrEntries[n] = entries[i];
                ++n;
            }

            max = nodeRight.GetNumEntries();
            entries = nodeRight.GetEntries();
            for (i = 0; i < nodeRight.GetNumEntries(); ++i)
            {
                arrEntries[n] = entries[i];
                ++n;
            }
            arrEntries[n] = newEntry;
            ++n;

            //Clear nodeLeft and nodeRight
            nodeLeft.SetNumEntries(0);
            nodeRight.SetNumEntries(0);

            //Redistribute(like SplitKeyDim)
            SortKeyDim(arrEntries, n, rootEntry.GetKey().GetDNO());

            max = (n >> 1);
            for (i = 0; i < max; ++i)
            {
                if (newEntry == arrEntries[i])
                    nodeLeft.AddEntry(arrEntries[i], true);//Add and update radius of arrNodes[i]
                else
                    nodeLeft.AddEntry(arrEntries[i]);
            }


            for (i = max; i < n; ++i)
            {
                if (newEntry == arrEntries[i])
                    nodeRight.AddEntry(arrEntries[i], true);//Add and update radius of arrNodes[i]
                else
                    nodeRight.AddEntry(arrEntries[i]);
            }

            float lMax = float.MinValue;
            float lMin = float.MaxValue;
            FindMaxMinDimVal(nodeLeft, rootEntry.GetKey().GetDNO(), ref lMax, ref lMin);

            float rMax = float.MinValue;
            float rMin = float.MaxValue;
            FindMaxMinDimVal(nodeRight, rootEntry.GetKey().GetDNO(), ref rMax, ref rMin);

            //Update key dimension lMax, rMin
            if (nodeLeft.GetNumEntries() > 0)
                rootEntry.SetLeftMax(lMax);

            if (nodeRight.GetNumEntries() > 0)
                rootEntry.SetRightMin(rMin);

            WriteNode(rootEntry.GetNode());
            WriteNode(nodeLeft);
            WriteNode(nodeRight);

            UpdateRadiusAndKeyDim(newEntry.GetNode().GetPage(), newEntry.GetPos());
        }

        private void FindMaxMinDimVal(MPNode<Key> node, int dim, ref float max, ref float min)
        {
            if (!node.IsLeaf())
            {
                int numEntries = node.GetNumEntries();
                MPEntry<Key>[] entries = node.GetEntries();
                MPNode<Key> nodeLeft;
                MPNode<Key> nodeRight;
                for (int i = 0; i < numEntries; ++i)
                {
                    nodeLeft = ReadNode(entries[i].GetLeftPage());
                    FindMaxMinDimVal(nodeLeft, dim, ref max, ref min);

                    nodeRight = ReadNode(entries[i].GetRightPage());
                    FindMaxMinDimVal(nodeRight, dim, ref max, ref min);
                }
            }
            else
            {
                int numEntries = node.GetNumEntries();
                MPEntry<Key>[] entries = node.GetEntries();
                float value;
                for (int i = 0; i < numEntries; ++i)
                {
                    value = entries[i].GetKey().GetDimensionValue(dim);
                    if (value > max)
                        max = value;

                    if (value < min)
                        min = value;
                }
            }
        }

        #endregion

        #region Split none root
        //-----------------------------------------------------------------------------------------------------------------
        //Promote
        private void EvalRadiusHyperplaneBased(MPEntry<Key> Op, MPEntry<Key> newEntry, MPEntry<Key> Op1, MPEntry<Key> Op2, out float rad1, out float rad2)
        {
	        int i;
	        float d1;
	        float d2;
	        rad1 = 0;
	        rad2 = 0;

	        //left node
            MPNode<Key> pN;
            ulong leftPage = Op.GetLeftPage();
            ulong rightPage = Op.GetRightPage();
            int n;
            MPEntry<Key>[] entries;
	        if(leftPage != 0)
	        {
                pN = ReadNode(leftPage);
                n = pN.GetNumEntries();
                entries = pN.GetEntries();
		        for(i = 0; i < n; ++i)
		        {
			        //if(Op1->data != pN.arrNode[i].data && Op2->data != pN.arrNode[i].data)
			        //{
                        d1 = Op1.GetKey().Distance(entries[i].GetKey());
                        d2 = Op2.GetKey().Distance(entries[i].GetKey());

				        if(d1 <= d2)
				        {
					        if(d1 > rad1)
						        rad1 = d1;
				        }
				        else
				        {
					        if(d2 > rad2)
						        rad2 = d2;
				        }
			        //}
		        }
	        }

	
	        //right node
	        if(rightPage != 0)
	        {
                pN = ReadNode(rightPage);
                n = pN.GetNumEntries();
                entries = pN.GetEntries();
		        for(i = 0; i < n; ++i)
		        {
			        //if(Op1->data != pN.arrNode[i].data && Op2->data != pN.arrNode[i].data)
			        //{
                        d1 = Op1.GetKey().Distance(entries[i].GetKey());
                        d2 = Op2.GetKey().Distance(entries[i].GetKey());

				        if(d1 <= d2)
				        {
					        if(d1 > rad1)
						        rad1 = d1;
				        }
				        else
				        {
					        if(d2 > rad2)
						        rad2 = d2;
				        }
			        //}
		        }
	        }


	        //Distribute newEntry
	        //if(Op1->data != newEntry->data && Op2->data != newEntry->data)
	        //{
                d1 = Op1.GetKey().Distance(newEntry.GetKey());
                d2 = Op2.GetKey().Distance(newEntry.GetKey());

		        if(d1 <= d2)
		        {
			        if(d1 > rad1)
				        rad1 = d1;
		        }
		        else
		        {
			        if(d2 > rad2)
				        rad2 = d2;
		        }
	        //}
        }

        // Use mM_RAD policy - Minimizes the maximum of the two raddi - Find Op1, Op2 satify MAX(r(Op1), r(Op2)) is minimum
        private void mM_RAD_Promote(MPEntry<Key> Op, MPEntry<Key> newEntry, out MPEntry<Key> Op1, out MPEntry<Key> Op2)
        {
            ulong leftPage = Op.GetLeftPage();
            ulong rightPage = Op.GetRightPage();
            MPNode<Key> nodeLeft;
            MPNode<Key> nodeRight;
            if (leftPage != 0)
                nodeLeft = ReadNode(leftPage);
            else
                nodeLeft = null;

            if (rightPage != 0)
                nodeRight = ReadNode(rightPage);
            else
                nodeRight = null;

	        int i;
	        int j;
	        float rad1;
	        float rad2;

            MPEntry<Key> p1 = null;
            MPEntry<Key> p2 = null;
	        float mM = float.MaxValue;
	        float tmp;

            int numEntriesLeft;
            int numEntriesRight;
            MPEntry<Key>[] entriesLeft;
            MPEntry<Key>[] entriesRight;
	        if(nodeLeft != null)
	        {
                entriesLeft = nodeLeft.GetEntries();
                numEntriesLeft = nodeLeft.GetNumEntries();
                
                for (i = 0; i < numEntriesLeft; ++i)
		        {
                    for (j = i + 1; j < numEntriesLeft; ++j)
			        {

                        EvalRadiusHyperplaneBased(Op, newEntry, entriesLeft[i], entriesLeft[j], out rad1, out rad2);
				
				        if(p1 == null && p2 == null)
				        {
					        mM = (rad1 > rad2) ? rad1 : rad2;
                            p1 = entriesLeft[i];
                            p2 = entriesLeft[j];
				        }
				        else
				        {
					        tmp = (rad1 > rad2) ? rad1 : rad2;
					        if(tmp < mM)
					        {
						        mM = tmp;
                                p1 = entriesLeft[i];
                                p2 = entriesLeft[j];
					        }
				        }
			        }

			        if(nodeRight != null)
			        {
                        entriesRight = nodeRight.GetEntries();
                        numEntriesRight = nodeRight.GetNumEntries();
                        for (j = 0; j < numEntriesRight; ++j)
				        {
                            EvalRadiusHyperplaneBased(Op, newEntry, entriesLeft[i], entriesRight[j], out rad1, out rad2);

					        if(p1 == null && p2 == null)
					        {
						        mM = (rad1 > rad2) ? rad1 : rad2;
                                p1 = entriesLeft[i];
                                p2 = entriesRight[j];
					        }
					        else
					        {
						        tmp = (rad1 > rad2) ? rad1 : rad2;
						        if(tmp < mM)
						        {
							        mM = tmp;
                                    p1 = entriesLeft[i];
                                    p2 = entriesRight[j];
						        }
					        }
				        }
			        }

                    EvalRadiusHyperplaneBased(Op, newEntry, entriesLeft[i], newEntry, out rad1, out rad2);
			        if(p1 == null && p2 == null)
			        {
				        mM = (rad1 > rad2) ? rad1 : rad2;
                        p1 = entriesLeft[i];
				        p2 = newEntry;
			        }
			        else
			        {
				        tmp = (rad1 > rad2) ? rad1 : rad2;
				        if(tmp < mM)
				        {
					        mM = tmp;
                            p1 = entriesLeft[i];
					        p2 = newEntry;
				        }
			        }
		        }
	        }


	        if(nodeRight != null)
	        {
                entriesRight = nodeRight.GetEntries();
                numEntriesRight = nodeRight.GetNumEntries();
		        for(i = 0; i < numEntriesRight; ++i)
		        {
                    for (j = i + 1; j < numEntriesRight; ++j)
			        {
                        EvalRadiusHyperplaneBased(Op, newEntry, entriesRight[i], entriesRight[j], out rad1, out rad2);
				
				        if(p1 == null && p2 == null)
				        {
					        mM = (rad1 > rad2) ? rad1 : rad2;
                            p1 = entriesRight[i];
                            p2 = entriesRight[j];
				        }
				        else
				        {
					        tmp = (rad1 > rad2) ? rad1 : rad2;
					        if(tmp < mM)
					        {
						        mM = tmp;
                                p1 = entriesRight[i];
                                p2 = entriesRight[j];
					        }
				        }
			        }

                    EvalRadiusHyperplaneBased(Op, newEntry, entriesRight[i], newEntry, out rad1, out rad2);
			        if(p1 == null && p2 == null)
			        {
				        mM = (rad1 > rad2) ? rad1 : rad2;
                        p1 = entriesRight[i];
				        p2 = newEntry;
			        }
			        else
			        {
				        tmp = (rad1 > rad2) ? rad1 : rad2;
				        if(tmp < mM)
				        {
					        mM = tmp;
                            p1 = entriesRight[i];
					        p2 = newEntry;
				        }
			        }
		        }
	        }

	        //Init Op1
            Op1 = new MPEntry<Key>();
            Op1.SetKey(p1.GetKey().Clone());

            MPNode<Key> pLeft = new MPNode<Key>(MAX_NUM_ENTRIES, Op.GetNode().GetLevel() - 1);
            MPNode<Key> pRight = new MPNode<Key>(MAX_NUM_ENTRIES, Op.GetNode().GetLevel() - 1);

            pLeft.SetPage(store.Allocate());
            pRight.SetPage(store.Allocate());
	
	        Op1.SetLeftPage(pLeft.GetPage());
            Op1.SetRightPage(pRight.GetPage());

	        pLeft.SetSiblingPage(pRight.GetPage());
	        pRight.SetSiblingPage(pLeft.GetPage());

            WriteNode(pLeft);
            WriteNode(pRight);

	        //Init Op2
            Op2 = new MPEntry<Key>();
            Op2.SetKey(p2.GetKey().Clone());

            pLeft = new MPNode<Key>(MAX_NUM_ENTRIES, Op.GetNode().GetLevel() - 1);
            pRight = new MPNode<Key>(MAX_NUM_ENTRIES, Op.GetNode().GetLevel() - 1);

            pLeft.SetPage(store.Allocate());
            pRight.SetPage(store.Allocate());

            Op2.SetLeftPage(pLeft.GetPage());
            Op2.SetRightPage(pRight.GetPage());

            pLeft.SetSiblingPage(pRight.GetPage());
            pRight.SetSiblingPage(pLeft.GetPage());

            WriteNode(pLeft);
            WriteNode(pRight);
        }

        //Generalized Hyperplane method
        private void Partition(MPEntry<Key> Op, MPEntry<Key> Op1, MPEntry<Key> Op2, MPEntry<Key> newEntry,
                       out MPEntry<Key>[] arrP1, out int nP1, out MPEntry<Key>[] arrP2, out int nP2)
        {
            arrP1 = new MPEntry<Key>[MAX_NUM_ENTRIES << 1];
            arrP2 = new MPEntry<Key>[MAX_NUM_ENTRIES << 1];
	        nP1 = 0;
	        nP2 = 0;

            LinkedList<MPKey> listKey1 = new LinkedList<MPKey>();
            LinkedList<MPKey> listKey2 = new LinkedList<MPKey>();

	        int i;
	        float d1;
	        float d2;

	        //Distribute left node
	        MPNode<Key> pN;
            ulong leftPage = Op.GetLeftPage();
            ulong rightPage = Op.GetRightPage();
            int numEntries;
            MPEntry<Key>[] entries;
	        if(leftPage != 0)
	        {
                pN = ReadNode(leftPage);
                numEntries = pN.GetNumEntries();
                entries = pN.GetEntries();
		        for(i = 0; i < numEntries; ++i)
		        {
                    d1 = Op1.GetKey().Distance(entries[i].GetKey());
                    d2 = Op2.GetKey().Distance(entries[i].GetKey());

				    if(d1 <= d2 && nP1 < arrP1.Length)
				    {
					    arrP1[nP1] = entries[i];
					    ++nP1;
                        listKey1.AddLast(entries[i].GetKey());
				    }
				    else
				    {
					    arrP2[nP2] = entries[i];
					    ++nP2;
                        listKey2.AddLast(entries[i].GetKey());
				    }
		        }
	        }

	
	        //Distribute right node
	        if(rightPage != 0)
	        {
                pN = ReadNode(rightPage);
                numEntries = pN.GetNumEntries();
                entries = pN.GetEntries();
		        for(i = 0; i < numEntries; ++i)
		        {
                    d1 = Op1.GetKey().Distance(entries[i].GetKey());
                    d2 = Op2.GetKey().Distance(entries[i].GetKey());

                    if (d1 <= d2 && nP1 < arrP1.Length)
				    {
					    arrP1[nP1] = entries[i];
					    ++nP1;
                        listKey1.AddLast(entries[i].GetKey());
				    }
				    else
				    {
					    arrP2[nP2] = entries[i];
					    ++nP2;
                        listKey2.AddLast(entries[i].GetKey());
				    }
		        }
	        }

	        //Distribute newEntry
            d1 = Op1.GetKey().Distance(newEntry.GetKey());
            d2 = Op2.GetKey().Distance(newEntry.GetKey());

            if (d1 <= d2 && nP1 < arrP1.Length)
		    {
			    arrP1[nP1] = newEntry;
			    ++nP1;
                listKey1.AddLast(newEntry.GetKey());
		    }
		    else
		    {
			    arrP2[nP2] = newEntry;
			    ++nP2;
                listKey2.AddLast(newEntry.GetKey());
		    }

            //Setup DNO
            Op1.GetKey().SetUpDNO(listKey1);
            Op2.GetKey().SetUpDNO(listKey2);
        }

        //------------------------------------------------------------------------------------
        //
        // Use selection sort
        private void SortKeyDim(MPEntry<Key>[] entries, int n, int dimension)
        {
            int i;
            int j;
            int pos;

            MPEntry<Key> tmp;

            for (i = 0; i < n; ++i)
            {
                pos = i;

                for (j = i + 1; j < n; ++j)
                {
                    if (entries[pos].GetKey().GetDimensionValue(dimension) > entries[j].GetKey().GetDimensionValue(dimension))
                        pos = j;
                }

                if (pos != i)
                {
                    tmp = entries[pos];
                    entries[pos] = entries[i];
                    entries[i] = tmp;
                }
            }
        }

        private void KeyDimSplit(MPEntry<Key> node, MPEntry<Key>[] arrNodes, int n, MPEntry<Key> newEntry)
        {
            SortKeyDim(arrNodes, n, node.GetKey().GetDNO());
            int i;
            int max = (n >> 1);

            //float lMax = float.MinValue;
            //float rMin = float.MaxValue;

            MPNode<Key> nodeLeft = ReadNode(node.GetLeftPage());
            for (i = 0; i < max; ++i)
            {
                if(newEntry == arrNodes[i])
                    nodeLeft.AddEntry(arrNodes[i], true);//Add and update radius of arrNodes[i]
                else
                    nodeLeft.AddEntry(arrNodes[i]);

                ////calc lMax
                //if (lMax < arrNodes[i].GetKey().GetDimensionValue(node.GetKey().GetDNO()) + arrNodes[i].GetRadius())
                //    lMax = arrNodes[i].GetKey().GetDimensionValue(node.GetKey().GetDNO()) + arrNodes[i].GetRadius();
            }

            MPNode<Key> nodeRight = ReadNode(node.GetRightPage());
            for (i = max; i < n; ++i)
            {
                if (newEntry == arrNodes[i])
                    nodeRight.AddEntry(arrNodes[i], true);//Add and update radius of arrNodes[i]
                else
                    nodeRight.AddEntry(arrNodes[i]);

                ////calc rMin
                //if (rMin > arrNodes[i].GetKey().GetDimensionValue(node.GetKey().GetDNO()) - arrNodes[i].GetRadius())
                //    rMin = arrNodes[i].GetKey().GetDimensionValue(node.GetKey().GetDNO()) - arrNodes[i].GetRadius();
            }

            float lMax = float.MinValue;
            float lMin = float.MaxValue;
            FindMaxMinDimVal(nodeLeft, node.GetKey().GetDNO(), ref lMax, ref lMin);

            float rMax = float.MinValue;
            float rMin = float.MaxValue;
            FindMaxMinDimVal(nodeRight, node.GetKey().GetDNO(), ref rMax, ref rMin);

            //Update key dimension lMax, rMin
            if (nodeLeft.GetNumEntries() > 0)
                node.SetLeftMax(lMax);

            if (nodeRight.GetNumEntries() > 0)
                node.SetRightMin(rMin);

            //// Determine if the left and right subtwin of a node are leaves or not
            //if (entry1 != null && (entry1.GetLeftPage() == 0 &&
            //    entry1.GetRightPage() == 0))
            //{
            //    nodeLeft.SetLevel(0);
            //    nodeRight.SetLevel(0);
            //}
            //else if (entry2 != null && (entry2.GetLeftPage() == 0 &&
            //    entry2.GetRightPage() == 0))
            //{
            //    nodeLeft.SetLevel(0);
            //    nodeRight.SetLevel(0);
            //}

            WriteNode(nodeLeft);
            WriteNode(nodeRight);
        }

        
        private void SplitNode(MPEntry<Key> root, MPEntry<Key> newEntry)
        {
            MPEntry<Key> Op1;
            MPEntry<Key> Op2;
            mM_RAD_Promote(root, newEntry, out Op1, out Op2);

            MPEntry<Key>[] arrP1 = null;
            MPEntry<Key>[] arrP2 = null;
            int nP1;
            int nP2;
            Partition(root, Op1, Op2, newEntry, out arrP1, out nP1, out arrP2, out nP2);

            KeyDimSplit(Op1, arrP1, nP1, newEntry);
            KeyDimSplit(Op2, arrP2, nP2, newEntry);


            //-------------------------------------------
            //Store Op1 and Op2 to the tree

            MPNode<Key> storedRootNode = root.GetNode();
            // Replace Op with Op1
            store.Deallocate(root.GetLeftPage());
            store.Deallocate(root.GetRightPage());

            storedRootNode.Replace(Op1, root.GetPos(), true);
            WriteNode(storedRootNode);
            UpdateRadiusAndKeyDim(storedRootNode.GetPage(), Op1.GetPos());
            if (!storedRootNode.IsFull())//Np is not full
            {
                //Store Op2 to storedNode if it is not full
                storedRootNode.AddEntry(Op2, true);
                WriteNode(storedRootNode);
                UpdateRadiusAndKeyDim(storedRootNode.GetPage(), Op2.GetPos());
            }
            else//Np is Full
            {
                ulong siblingPage = storedRootNode.GetSiblingPage();

                MPNode<Key> siblingNode = null;
                if (siblingPage != 0)
                    siblingNode = ReadNode(siblingPage);

                MPNode<Key> parentNode = ReadNode(storedRootNode.GetParentPage());
                MPEntry<Key> parentEntry = parentNode.GetEntries()[storedRootNode.GetParentPos()];

                if (siblingNode == null || siblingNode.IsFull())//siblingNode is full or siblingPage == 0 (in case of root is THE ROOT OF TREE)
                {
                    Split(parentEntry, Op2);
                }
                else
                {
                    Reallocate(parentEntry, Op2);
                }
            }
        }

        //private void SplitNode(MPEntry<Key> root, MPEntry<Key> newEntry)
        //{
        //    MPEntry<Key> Op1;
        //    MPEntry<Key> Op2;
        //    mM_RAD_Promote(root, newEntry, out Op1, out Op2);

        //    MPEntry<Key>[] arrP1 = null;
        //    MPEntry<Key>[] arrP2 = null;
        //    int nP1;
        //    int nP2;
        //    Partition(root, Op1, Op2, newEntry, out arrP1, out nP1, out arrP2, out nP2);

        //    KeyDimSplit(Op1, arrP1, nP1, newEntry);
        //    KeyDimSplit(Op2, arrP2, nP2, newEntry);

        //    if (root.GetRightPage() == 0)//root is the ROOT OF TREE
        //    {
        //        root.SetKey(Op1.GetKey().Clone());
        //        root.GetKey().SetDNO(-1);
        //        root.SetDisToParent(0);
        //        root.SetLeftMax(float.MinValue);
        //        root.SetRightMin(float.MaxValue);
        //        root.GetNode().SetParentPage(0);
        //        root.SetRadius(0);
        //        WriteNode(root.GetNode());

        //        MPNode<Key> nodeLeft = ReadNode(root.GetLeftPage());
        //        nodeLeft.SetNumEntries(0);
        //        CURRENT_LEVEL = nodeLeft.GetLevel() + 1;
        //        nodeLeft.SetLevel(CURRENT_LEVEL);
        //        nodeLeft.AddEntry(Op1, true);
        //        nodeLeft.AddEntry(Op2, true);
        //        WriteNode(nodeLeft);

        //        UpdateRadiusAndKeyDim(root.GetNode().GetPage(), Op1.GetPos());
        //        UpdateRadiusAndKeyDim(root.GetNode().GetPage(), Op2.GetPos());

        //        /*
        //        ///////////////////////////
        //        //Update Op1->left, Op1->right, Op2->left, Op2->right
        //        MPNode tmpNode = ReadNode(Op1.GetLeftPage());
        //        tmpNode.SetParentPage(Op1.GetNode().GetPage());
        //        tmpNode.SetParentPos(Op1.GetPos());
        //        WriteNode(tmpNode);

        //        tmpNode = ReadNode(Op1.GetRightPage());
        //        tmpNode.SetParentPage(Op1.GetNode().GetPage());
        //        tmpNode.SetParentPos(Op1.GetPos());
        //        WriteNode(tmpNode);

        //        tmpNode = ReadNode(Op2.GetLeftPage());
        //        tmpNode.SetParentPage(Op2.GetNode().GetPage());
        //        tmpNode.SetParentPos(Op2.GetPos());
        //        WriteNode(tmpNode);

        //        tmpNode = ReadNode(Op2.GetRightPage());
        //        tmpNode.SetParentPage(Op2.GetNode().GetPage());
        //        tmpNode.SetParentPos(Op2.GetPos());
        //        WriteNode(tmpNode);
        //         * */
        //    }
        //    else
        //    {
        //        MPNode<Key> storedRootNode = root.GetNode();

        //        // Replace Op with Op1
        //        store.Deallocate(root.GetLeftPage());
        //        store.Deallocate(root.GetRightPage());

        //        storedRootNode.Replace(Op1, root.GetPos(), true);
        //        WriteNode(storedRootNode);
        //        UpdateRadiusAndKeyDim(storedRootNode.GetPage(), Op1.GetPos());

        //        /*
        //        //------------------------------------------------------
        //        //Update parent of Op1->leftPage and Op1->rightPage
        //        MPNode tmpNode = ReadNode(Op1.GetLeftPage());
        //        tmpNode.SetParent(Op1.GetNode().GetPage(), Op1.GetPos());
        //        WriteNode(tmpNode);

        //        tmpNode = ReadNode(Op1.GetRightPage());
        //        tmpNode.SetParent(Op1.GetNode().GetPage(), Op1.GetPos());
        //        WriteNode(tmpNode);
        //        */

        //        if (!storedRootNode.IsFull())//Np is not full
        //        {
        //            //Store Op2 to storedNode if it is not full
        //            storedRootNode.AddEntry(Op2, true);
        //            WriteNode(storedRootNode);
        //            UpdateRadiusAndKeyDim(storedRootNode.GetPage(), Op2.GetPos());
        //            //------------------------------------------------------
        //            //Update parent of Op2->leftPage and Op2->rightPage
        //            /*
        //            tmpNode = ReadNode(Op2.GetLeftPage());
        //            tmpNode.SetParent(Op2.GetNode().GetPage(), Op2.GetPos());
        //            WriteNode(tmpNode);

        //            tmpNode = ReadNode(Op2.GetRightPage());
        //            tmpNode.SetParent(Op2.GetNode().GetPage(), Op2.GetPos());
        //            WriteNode(tmpNode);
        //             * */
        //        }
        //        else//Np is Full
        //        {
        //            ulong siblingPage = storedRootNode.GetSiblingPage();

        //            MPNode<Key> siblingNode = null;
        //            if (siblingPage != 0)
        //                siblingNode = ReadNode(siblingPage);

        //            MPNode<Key> parentNode = ReadNode(storedRootNode.GetParentPage());
        //            MPEntry<Key> parentEntry = parentNode.GetEntries()[storedRootNode.GetParentPos()];

        //            if (siblingNode == null || siblingNode.IsFull())//siblingNode is full or siblingPage == 0 (in case of root is THE ROOT OF TREE)
        //            {
        //                Split(parentEntry, Op2);
        //            }
        //            else
        //            {
        //                Reallocate(parentEntry, Op2);
        //            }
        //        }
        //    }
        //}

        #endregion

        #region Split root
        //-----------------------------------------------------------------------------------------
        //Split root
        private void PromoteRoot(MPEntry<Key>[] entries, int n, int rootLevel, out MPEntry<Key> Op)
        {
            int i;
            int j;
            MPEntry<Key> choosedEntry = null;
            float radius = float.MinValue;
            float dist;
            float mM = float.MaxValue;
            for (i = 0; i < n; ++i)
            {
                //Calculate radius
                for (j = 0; j < n; ++j)
                {
                    dist = entries[i].GetKey().Distance(entries[j].GetKey());
                    if (radius < dist)
                        radius = dist;
                }

                if (choosedEntry == null)
                {
                    choosedEntry = entries[i];
                    mM = radius;
                }
                else
                {
                    if (mM > radius)
                    {
                        mM = radius;
                        choosedEntry = entries[i];
                    }
                }
            }

            //Init Op
            Op = new MPEntry<Key>();
            Op.SetKey(choosedEntry.GetKey().Clone());

            MPNode<Key> pLeft = new MPNode<Key>(MAX_NUM_ENTRIES, rootLevel - 1);
            MPNode<Key> pRight = new MPNode<Key>(MAX_NUM_ENTRIES, rootLevel - 1);

            pLeft.SetPage(store.Allocate());
            pRight.SetPage(store.Allocate());

            Op.SetLeftPage(pLeft.GetPage());
            Op.SetRightPage(pRight.GetPage());

            pLeft.SetSiblingPage(pRight.GetPage());
            pRight.SetSiblingPage(pLeft.GetPage());

            WriteNode(pLeft);
            WriteNode(pRight);
        }
        
        private void SplitRoot(MPEntry<Key> root, MPEntry<Key> newEntry)
        {
            if (IsRoot(root.GetNode()))
            {
                MPNode<Key> leftNode = ReadNode(root.GetLeftPage());
                MPEntry<Key>[] entries = leftNode.GetEntries();
                int n = leftNode.GetNumEntries();
                MPEntry<Key>[] arrP = new MPEntry<Key>[n + 1];
                MPKey[] arrKey = new MPKey[n + 1];
                int i;
                for (i = 0; i < n; ++i)
                {
                    arrP[i] = entries[i];
                    arrKey[i] = entries[i].GetKey();
                }

                arrP[i] = newEntry;
                arrKey[i] = newEntry.GetKey();

                //Promote
                MPEntry<Key> Op;
                PromoteRoot(arrP, n + 1, root.GetNode().GetLevel(), out Op);

                //Setup key dimension number
                Op.GetKey().SetUpDNO(arrKey);

                //Split by key dimension
                KeyDimSplit(Op, arrP, n + 1, newEntry);

                //Update root
                ++CURRENT_LEVEL;
                root.SetKey(Op.GetKey().Clone());
                root.GetKey().SetDNO(-1);
                root.SetDisToParent(0);
                root.SetLeftMax(float.MinValue);
                root.SetRightMin(float.MaxValue);
                root.GetNode().SetParentPage(0);
                root.GetNode().SetLevel(CURRENT_LEVEL);
                root.SetRadius(0);
                WriteNode(root.GetNode());

                //Update root.left
                leftNode.SetNumEntries(0);
                leftNode.SetSiblingPage(0);
                leftNode.SetLevel(leftNode.GetLevel() + 1);
                leftNode.AddEntry(Op, true);
                WriteNode(leftNode);

                UpdateRadiusAndKeyDim(leftNode.GetPage(), Op.GetPos());
            }
        }

        #endregion

        #region Split
        //--------------------------------------------------------------------------------------
        //Split
        private void Split(MPEntry<Key> parentEntry, MPEntry<Key> newEntry)
        {
            if (IsRoot(parentEntry.GetNode()))
            {
                SplitRoot(parentEntry, newEntry);
            }
            else
            {
                SplitNode(parentEntry, newEntry);
            }
        }
        
        #endregion

        #region Insert
        public MPNode<Key> ChooseSubTree(MPNode<Key> root, MPEntry<Key> entry)
        {
            /*
            MPNode<Key> root = ReadNode(rootAddr);

            MPEntry<Key> choosedEntry = null;

            float curDist = float.MaxValue;
            float d;
            int pos;

            MPEntry<Key>[] entries = root.GetEntries();

            int i;
            for (i = 0; i < root.GetNumEntries(); ++i)
            {
                d = entry.GetKey().Distance(entries[i].GetKey());
                if (d < curDist)
                {
                    choosedEntry = entries[i];
                    curDist = d;
                    pos = i;
                }
            }

            */

            MPEntry<Key> choosedEntry = null;

            bool isIncrease = true;
            float minInDist = float.MaxValue;
            float minIncrease = float.MaxValue;
            float d;

            MPEntry<Key>[] entries = root.GetEntries();

            int i;
            for (i = 0; i < root.GetNumEntries(); ++i)
            {

                d = entry.GetKey().Distance(entries[i].GetKey());

                if (d <= entries[i].GetRadius())
                {
                    if (minInDist > d)
                    {
                        choosedEntry = entries[i];
                        minInDist = d;
                    }

                    if (isIncrease) isIncrease = false;
                }
                else if (isIncrease)
                {
                    if (minIncrease > d - entries[i].GetRadius())
                    {
                        choosedEntry = entries[i];
                        minIncrease = d - entries[i].GetRadius();
                    }
                }
            }

            //Choose TwinNode
            MPNode<Key> choosedNode;
            MPNode<Key> leftNode = ReadNode(choosedEntry.GetLeftPage());
            MPNode<Key> rightNode = ReadNode(choosedEntry.GetRightPage());
            if (leftNode.GetNumEntries() == 0 && leftNode.IsLeaf())
            {
                //choosedPage = choosedEntry.GetLeftPage();
                choosedNode = leftNode;
            }
            else if (rightNode.GetNumEntries() == 0 && rightNode.IsLeaf())
            {
                //choosedPage = choosedEntry.GetRightPage();
                choosedNode = rightNode;
            }
            else if (choosedEntry.GetLeftMax() >= entry.GetKey().GetDimensionValue(choosedEntry.GetKey().GetDNO()))
            {
                //choosedPage = choosedEntry.GetLeftPage();
                choosedNode = leftNode;
            }
            else if (choosedEntry.GetRightMin() <= entry.GetKey().GetDimensionValue(choosedEntry.GetKey().GetDNO()))
            {
                //choosedPage = choosedEntry.GetRightPage();
                choosedNode = rightNode;
            }
            else
            {
                if (entry.GetKey().GetDimensionValue(choosedEntry.GetKey().GetDNO()) - choosedEntry.GetLeftMax() <=
                    choosedEntry.GetRightMin() - entry.GetKey().GetDimensionValue(choosedEntry.GetKey().GetDNO()))
                {
                    //choosedPage = choosedEntry.GetLeftPage();
                    choosedNode = leftNode;
                }
                else
                {
                    //choosedPage = choosedEntry.GetRightPage();
                    choosedNode = rightNode;
                }
            }

            return choosedNode;
        }

        //--------------------------------------------------------------------------------------
        //Insert entry
        private int Insert(MPNode<Key> root, MPEntry<Key> entry)//root must be not NULL
        {
            int resultFlag;
            if (!root.IsLeaf())//subroot is not leaf
            {
                MPNode<Key> subTree = ChooseSubTree(root, entry);
                resultFlag = Insert(subTree, entry);

                //if (resultFlag == 0 || resultFlag == 1)
                //{
                //    root = ReadNode(root.GetPage());
                //    //Update key dimension
                //    MPEntry<Key> pEntry = root.GetEntries()[subTreeRoot.GetParentPos()];
                //    float dimVal = entry.GetKey().GetDimensionValue(pEntry.GetKey().GetDNO());

                //    if (subTreePage == pEntry.GetLeftPage())
                //    {
                //        if (pEntry.GetLeftMax() < dimVal)
                //            pEntry.SetLeftMax(dimVal);
                //    }
                //    else
                //    {
                //        if (pEntry.GetRightMin() > dimVal)
                //            pEntry.SetRightMin(dimVal);
                //    }

                //    WriteNode(root);
                //}

                resultFlag = 0;
            }
            else //subroot is leaf
            {
                if (!root.IsFull())//not full
                {
                    StoreEntry(root, entry);
                    resultFlag = 1;
                }
                else
                {
                    ulong siblingPage = root.GetSiblingPage();

                    MPNode<Key> sibling = null;
                    if (siblingPage != 0)
                        sibling = ReadNode(siblingPage);

                    MPNode<Key> parentNode = ReadNode(root.GetParentPage());
                    MPEntry<Key> parentEntry = parentNode.GetEntries()[root.GetParentPos()];

                    if (sibling != null && !sibling.IsFull())//root's twin is not full
                    {
                        Reallocate(parentEntry, entry);
                        resultFlag = 2;
                    }
                    else
                    {
                        Split(parentEntry, entry);
                        resultFlag = 3;
                    }
                }
            }

            return resultFlag;
        }


        public void Insert(MPEntry<Key> entry)
        {
            if (IsOpen())
            {
                MPNode<Key> root = ReadNode(GetRootPage());
                Insert(root, entry);
                
                //if (entry.GetKey().GetDimensionValue(0) == 6)
                //{
                //    println("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee");
                //    MPNode<Key> node0 = ReadNode(GetRootPage());
                //    println(node0.GetNumEntries() + "," + node0.GetEntries()[0].GetRadius() + "," + node0.GetEntries()[0].GetKey().GetDimensionValue(0) + "," + node0.GetEntries()[0].GetLeftMax() + "," + node0.GetEntries()[0].GetRightMin());

                //    MPNode<Key> node1 = ReadNode(node0.GetEntries()[0].GetRightPage());
                //    MPNode<Key> node = ReadNode(node1.GetEntries()[1].GetRightPage());
                //    println(node.GetNumEntries() + "," + node.GetEntries()[0].GetKey().GetDimensionValue(0) + "," + node.GetEntries()[0].GetRadius() + "," + node.GetEntries()[0].GetLeftMax() + "," + node.GetEntries()[0].GetRightMin());
                //}
                
            }
        }

        #endregion

        #region Range query
        //-------------------------------------------------------------------------------------------
        //Range Searching

        private void RangeSearch(MPNode<Key> root, MPNode<Key> parentNode, MPQueryObj qObj, float rQ, LinkedList<MPKey> result)
        {
            if (root.GetNumEntries() == 0)
                return;
            
            MPEntry<Key> parentEntry = parentNode.GetEntries()[root.GetParentPos()];

	        float dPQ = parentEntry.GetKey().Distance(qObj.GetKey());
	        float dRQ;
	        if(!root.IsLeaf())//root is not leaf
	        {
		        int i;
                int numEntries = root.GetNumEntries();
                MPEntry<Key>[] entries = root.GetEntries();
		        for(i = 0; i < numEntries; ++i)
		        {
                    if (Math.Abs(dPQ - entries[i].GetDisToParent()) <= rQ + entries[i].GetRadius())
			        {
                        dRQ = entries[i].GetKey().Distance(qObj.GetKey());
				
				        if(dRQ <= rQ + entries[i].GetRadius())
				        {
                            float dimensionValue = qObj.GetKey().GetDimensionValue(entries[i].GetKey().GetDNO());
                            if (dimensionValue - rQ <= entries[i].GetLeftMax())
					        {
                                MPNode<Key> node = ReadNode(entries[i].GetLeftPage());
                                RangeSearch(node, root, qObj, rQ, result);
					        }

                            if (dimensionValue + rQ >= entries[i].GetRightMin())
					        {
                                MPNode<Key> node = ReadNode(entries[i].GetRightPage());
                                RangeSearch(node, root, qObj, rQ, result);
					        }
				        }
			        }
		        }
	        }
	        else
	        {
		        int i;
                int numEntries = root.GetNumEntries();
                MPEntry<Key>[] entries = root.GetEntries();
                for (i = 0; i < numEntries; ++i)
		        {
			        if(Math.Abs(dPQ - entries[i].GetDisToParent()) <= rQ)
			        {
				        if(entries[i].GetKey().Distance(qObj.GetKey()) <= rQ)
				        {
					        //add to result 
                            result.AddLast(entries[i].GetKey());
				        }
			        }
		        }
	        }
        }

        public void RangeSearch(MPQueryObj qObj, float rQ, LinkedList<MPKey> result)
        {
            MPNode<Key> root = ReadNode(GetRootPage());
            MPNode<Key> parentNode = ReadNode(root.GetParentPage());
            RangeSearch(root, parentNode, qObj, rQ, result);
        }

        #endregion

        #region k-Nearest query
        //-------------------------------------------------------------------------------------------
        //k-Nearest Searching
        #endregion

        #region DEBUG
        //Methods for debugging
        private void println(string s)
        {
            System.Console.WriteLine(s);
        }

        private void printNode(ulong page)
        {
            if (page != 0)
            {
                println("---start node---");
                MPNode<Key> node = ReadNode(page);
                for (int i = 0; i < node.GetNumEntries(); ++i)
                    System.Console.WriteLine(node.GetEntries()[i].GetKey().GetDimensionValue(0) + "," + node.GetEntries()[i].GetRadius() + "," + node.GetEntries()[i].GetLeftMax() + "," + node.GetEntries()[i].GetRightMin());
                println("---end node---");
            }
        }
        #endregion
    }
}
